Alice und Bob nutzen das Diffie-Hellman-Verfahren in $(\Z/17\Z)^*$ mit Erzeuger $3 + 17 \Z$.

\paragraph{Anwendung Diffie-Hellman im Normalfall}
Alice wählt $a= 3$, Bob $b=5$. Geben Sie die übertragenen Nachrichten und den Schlüssel an.

\textbf{Lösung}

Es gilt $a = 3$, $b = 5$, $p = 17$, $g = 3$.

\begin{enumerate}
\item Alice

Es gilt $A = g ^ a \tmod p = 3 ^ 3 \tmod 17$. Die Berechnung erfolgt mit Hilfe der schnellen Exponentiation. Die Binärentwicklung des Exponenten $3$ wird ermittelt. Sie ist $3 = 2 ^ 1 + 2 ^ 0$. Anschließend werden die sukzessiven Quadrate in $\mathbb{Z}/17\mathbb{Z}$ berechnet.

\begin{center}
\begin{tabular}{|c||c|}
\hline
\cellcolor{dunkelgrau}$3^{2^0}$ & \cellcolor{dunkelgrau}$3^{2^1}$ \\
\hline
\cellcolor{dunkelgrau}$3$ & \cellcolor{dunkelgrau}$3^2 = 9$ \\
\hline 
\end{tabular}
\end{center}

Somit ist $3 ^ 3 \tmod 17 = 3 ^ {2 ^ 0} \cdot 3 ^ {2 ^ 1} \tmod 17 = 3 \cdot 9 \tmod 17 \equiv 10 \tmod 17$.

\begin{center}
\uuline{$A = 10$}
\end{center}

\item Bob

Es gilt $B = g ^ b \tmod p = 3 ^ 5 \tmod 17$. Die Berechnung erfolgt mit Hilfe der schnellen Exponentiation. Die Binärentwicklung des Exponenten $5$ wird ermittelt. Sie ist $5 = 2 ^ 2 + 2 ^ 0$.

Die sukzessiven Quadrate in $\mathbb{Z}/17\mathbb{Z}$ sind

\begin{center}
\begin{tabular}{|c||c||c|}
\hline
\cellcolor{dunkelgrau}$3^{2^0}$ & $3^{2^1}$ & \cellcolor{dunkelgrau}$3^{2^2}$ \\
\hline
\cellcolor{dunkelgrau}$3$ & $3^2 = 9$ & \cellcolor{dunkelgrau}$9^2 \equiv 13$ \\
\hline 
\end{tabular}
\end{center}

Somit ist $3 ^ 5 \tmod 17 = 3 ^ {2 ^ 0} \cdot 3 ^ {2 ^ 2} \tmod 17 = 3 \cdot 13 \tmod 17 \equiv 5 \tmod 17$.

\begin{center}
\uuline{$B = 5$}
\end{center}

\item Schlüssel

Der Schlüssel kann auf beiden Seiten berechnet werden. Alice erhält den Schlüssel durch $B ^ a \tmod p$ und Bob durch $A ^ b \tmod p$. Ersteres wird nachfolgend ausgeführt. Die Berechnung von $5 ^ 3 \tmod 17$ erfolgt mit Hilfe der schnellen Exponentiation. Die Binärentwicklung des Exponenten $3$ ist bereits bekannt und lautet $3 = 2 ^ 1 + 2 ^ 0$. Anschließend werden die sukzessiven Quadrate in $\mathbb{Z}/17\mathbb{Z}$ berechnet.

\begin{center}
\begin{tabular}{|c||c|}
\hline
\cellcolor{dunkelgrau}$5^{2^0}$ & \cellcolor{dunkelgrau}$5^{2^1}$ \\
\hline
\cellcolor{dunkelgrau}$5$ & \cellcolor{dunkelgrau}$5^2 \equiv 8$ \\
\hline 
\end{tabular}
\end{center}

Somit ist $5 ^ 3 \tmod 17 = 5 ^ {2 ^ 0} \cdot 5 ^ {2 ^ 1} \tmod 17 = 5 \cdot 8 \tmod 17 \equiv 6 \tmod 17$.

\begin{center}
\uuline{Der Schlüssel zwischen Alice und Bob ist $6$}
\end{center}

\end{enumerate}

\paragraph{Anwendung Diffie-Hellman im Falle einer Man-in-the-middle-Attacke}

Ein Angreifer (Oskar) schafft es, sich in die Verbindung zwischen Alice und Bob einzuklinken. Er wählt den Exponenten $c = 4$. 
Geben Sie die übertragenen Nachrichten und die Schlüssel an. Unter welchen Umständen können Alice und Bob später erkennen, dass sie angegriffen wurden? Haben Sie eine Idee, wie einem solchen Angriff vorgebeugt werden kann?

\textbf{Lösung}

In diesem Fall kommunizieren Alice und Bob nicht direkt, sondern jeweils ausschließlich mit Oskar. Aus diesem Grund erfolgt der Diffie-Hellman-Schlüsseltausch zweimal. Es gibt dann einen Schlüssel zwischen Alice und Oskar und einen zwischen Oskar und Bob.

\begin{enumerate}

\item Oskar

Auf Seiten von Alice bleibt $A = 10$ und bei Bob gilt weiterhin $B = 5$. Nun berechnet Oskar $C$ indem er $c = 4$ wählt. Für ihn gilt $C = g ^ c \tmod p = 3 ^ 4 \tmod 17$. Das wird mit Hilfe der schnellen Exponentiation berechnet. Die Binärentwicklung des Exponenten $4$ wird ermittelt. Sie lautet $4 = 2 ^ 2$. Die sukzessiven Quadrate in $\mathbb{Z}/17\mathbb{Z}$ wurden bereits berechnet.

\begin{center}
\begin{tabular}{|c||c||c|}
\hline
$3^{2^0}$ & $3^{2^1}$ & \cellcolor{dunkelgrau}$3^{2^2}$ \\
\hline
$3$ & $3^2 = 9$ & \cellcolor{dunkelgrau}$9^2 \equiv 13$ \\
\hline 
\end{tabular}
\end{center}

Somit ist $3 ^ 4 \tmod 17 = 3 ^ {2 ^ 2} \tmod 17 = 13 \tmod 17$.

\begin{center}
\uuline{$C = 13$}
\end{center}

\item Schlüssel zwischen Alice und Oskar

Der Schlüssel kann auf beiden Seiten berechnet werden. Alice erhält den Schlüssel durch $C ^ a \tmod p$ und Oskar durch $A ^ c \tmod p$. Ersteres wird nachfolgend ausgeführt. Die Berechnung von $13 ^ 3 \tmod 17$ erfolgt mit Hilfe der schnellen Exponentiation. Die Binärentwicklung des Exponenten $3$ ist bereits bekannt und lautet $3 = 2 ^ 1 + 2 ^ 0$. Anschließend werden die sukzessiven Quadrate in $\mathbb{Z}/17\mathbb{Z}$ berechnet.

Die sukzessiven Quadrate in $\mathbb{Z}/17\mathbb{Z}$ sind

\begin{center}
\begin{tabular}{|c||c|}
\hline
\cellcolor{dunkelgrau}$13^{2^0}$ & \cellcolor{dunkelgrau}$13^{2^1}$ \\
\hline
\cellcolor{dunkelgrau}$13$ & \cellcolor{dunkelgrau}$13^2 \equiv 16$ \\
\hline 
\end{tabular}
\end{center}

Somit ist $13 ^ 3 \tmod 17 = 13 ^ {2 ^ 0} \cdot 13 ^ {2 ^ 1} \tmod 17 = 13 \cdot 16 \tmod 17 \equiv 4 \tmod 17$.

\begin{center}
\uuline{Der Schlüssel zwischen Alice und Oskar ist $4$}
\end{center}

\item Schlüssel zwischen Oskar und Bob

Der Schlüssel kann auf beiden Seiten berechnet werden. Oskar erhält den Schlüssel durch $B ^ c \tmod p$ und Bob durch $C ^ b \tmod p$. Ersteres wird nachfolgend ausgeführt. Die Berechnung von $5 ^ 4 \tmod 17$ erfolgt mit Hilfe der schnellen Exponentiation. Die Binärentwicklung des Exponenten $4$ ist bereits bekannt und lautet $4 = 2 ^ 2$.  Anschließend werden die sukzessiven Quadrate in $\mathbb{Z}/17\mathbb{Z}$ berechnet.

\begin{center}
\begin{tabular}{|c||c||c|}
\hline
$5^{2^0}$ & $5^{2^1}$ & \cellcolor{dunkelgrau}$5^{2^2}$ \\
\hline
$5$ & $5 ^ 2 \equiv 8$ & \cellcolor{dunkelgrau}$8^2 \equiv 13$ \\
\hline 
\end{tabular}
\end{center}

Somit ist $5 ^ 4 \tmod 17 = 5 ^ {2 ^ 2} \tmod 17 = 13 \tmod 17$.

\begin{center}
\uuline{Der Schlüssel zwischen Oskar und Bob ist $13$}
\end{center}

Alice und Bob erkennen den Angriff, sobald der Umweg über Oskar wegfällt. Kommunizieren sie wieder direkt, so nutzen sie unterschiedliche Schlüssel. Das hat den Effekt, dass die Entschlüsselung einer Nachricht zu keinem sinnhaften Ergebnis führt. Eine weitere Möglichkeit zur Entdeckung des Angriffs ist ein persönliches Treffen zwischen Alice und Bob, bei dem sie ihre Schlüssel abgleichen und feststellen, dass diese nicht übereinstimmen.

Einer Man-in-the-middle-Attacke kann vorgebeugt werden, indem für die Kommunikation im Rahmen des Schlüsseltauschs ein asymmetrisches Verschlüsselungsverfahren genutzt wird. Solange Oskar dieses nicht überwinden kann und keine Möglichkeit zur Beeinflussung des Verzeichnisses mit den öffentlichen Schlüssel der Teilnehmer hat, hat er auch keine Möglichkeit, sich unbemerkt in den Schlüsseltausch einzuklinken.

Noch besser ist die Nutzung elektronischer Signaturen.

\end{enumerate}
